#pragma once

#include <functional>
#include <vector>
#include <memory>
#include <algorithm>
#include <stdexcept>

class IGraph
{
public:
    virtual ~IGraph() { }

    virtual std::string get_name_of_method() const = 0;

    virtual size_t number_of_vertices() const = 0;
    virtual size_t number_of_edges() const = 0;

    virtual void clear() = 0;
    virtual void resize(size_t number_of_vertices) = 0;
    virtual void add_edge(int from_vertix, int to_vertix) = 0;
    virtual void remove_edge(int from_vertix, int to_vertix) = 0;

    virtual bool is_edged(int from_vertix, int to_vertix) const = 0;
	virtual void foreach_neighbour(int vertix, std::function <void(int)> visitor) const = 0;


    virtual size_t byte_size() const = 0;
    virtual size_t byte_size(size_t number_of_vertices, size_t number_of_edges) const = 0;
};

class MatrixGraph: public IGraph
{
    std::vector < std::vector <bool> > graph_;
public:
    explicit MatrixGraph(size_t number_of_vertices = 0)
    {
        graph_.resize(number_of_vertices);
        for (auto it = graph_.begin(); it != graph_.end(); it++)
            (*it).resize(number_of_vertices);
    }
    explicit MatrixGraph(const std::vector <std::vector <bool> > &graph): graph_(graph)
    {
        for (auto it = graph_.begin(); it != graph_.end(); it++)
            if (it -> size() != graph_.size())
                throw std::runtime_error("MatrixGraph: input matrix is not square");
    }
    ~MatrixGraph()
    {
        graph_.clear();
    }

    std::string get_name_of_method() const
    {
        return "matrix graph";
    }

    size_t number_of_vertices() const { return graph_.size(); }
    size_t size() const {return number_of_vertices(); }
    size_t number_of_edges() const
    {
        size_t number_of_edges = 0;
        for (auto i = graph_.begin(); i != graph_.end(); i++)
            for (auto j = i -> begin(); j != i -> end(); j++)
                number_of_edges += *j;
        return number_of_edges;
    }

    void clear() { graph_.clear(); }
    void resize(size_t number_of_vertices)
    {
        graph_.resize(number_of_vertices);
        for (auto it = graph_.begin(); it != graph_.end(); it++)
            (*it).resize(number_of_vertices);
    }
    void add_edge(int from_vertix, int to_vertix) { graph_.at(from_vertix).at(to_vertix) = 1; }
    void remove_edge(int from_vertix, int to_vertix) { graph_.at(from_vertix).at(to_vertix) = 0; }
    void construct_by_matrix(const std::vector < std::vector <bool> > &graph)
    {
        clear();
        graph_ = graph;
    }
    void construct_by_list(const std::vector < std::vector <int> > &graph)
    {
        clear();
        graph_.resize(graph.size());
        for (size_t node = 0; node < graph.size(); node++)
        {
            graph_.at(node).resize(graph.size());
            for (size_t i = 0; i < graph.size(); i++)
                graph_.at(node).at(i) = 0;
            for (size_t to = 0; to < graph.at(node).size(); to++)
                graph_.at(node).at(graph.at(node).at(to)) = 1;
        }
    }

    void foreach_neighbour(int vertix, std::function <void(int)> visitor) const
    {
        for (size_t index = 0; index < graph_.size(); index++)
            if (graph_.at(vertix).at(index))
                visitor(index);
    }
    bool is_edged(int from_vertix, int to_vertix) const { return graph_.at(from_vertix).at(to_vertix); }

    size_t byte_size() const
    {
        return sizeof(std::vector< std::vector <bool> >) + sizeof(std::vector <bool> ) * graph_.capacity() +
               graph_.capacity() * graph_.size() / 8 + 1;
    }
    size_t byte_size(size_t number_of_vertices, size_t number_of_edges) const
    {
        return sizeof(std::vector< std::vector <bool> >) + sizeof(std::vector <bool> ) * number_of_vertices +
               number_of_vertices * number_of_vertices / 8 + 1;
    }
};


class ListGraph: public IGraph
{
    std::vector < std::vector <int> > graph_;
public:
    explicit ListGraph(size_t number_of_vertices = 0)
    {
        graph_.resize(number_of_vertices);
    }
    explicit ListGraph(const std::vector <std::vector <int> > &graph): graph_(graph) {}
    ~ListGraph()
    {
        graph_.clear();
    }

    std::string get_name_of_method() const
    {
        return "list graph";
    }

    size_t number_of_vertices() const { return graph_.size(); }
    size_t size() const {return number_of_vertices(); }
    size_t number_of_edges() const
    {
        size_t number_of_edges = 0;
        for (auto it = graph_.begin(); it != graph_.end(); it++)
            number_of_edges += it -> size();
        return number_of_edges;
    }

    void clear() { graph_.clear(); }
    void resize(size_t number_of_vertices)
    {
        graph_.resize(number_of_vertices);
    }
    void add_edge(int from_vertix, int to_vertix)
    {
        if (to_vertix < 0 || to_vertix >= graph_.size())
            throw std::runtime_error("ListGraph: add_edge: the end of the edge doesn't exist in the graph");
        for (auto it = graph_.at(from_vertix).begin(); it != graph_.at(from_vertix).end(); it++)
            if (*it == to_vertix)
                return;
        graph_.at(from_vertix).push_back(to_vertix);
    }
    void remove_edge(int from_vertix, int to_vertix)
    {
        if (to_vertix < 0 || to_vertix >= graph_.size())
            throw std::runtime_error("ListGraph: remove_edge: the end of the edge doesn't exist in the graph");
        for (auto it = graph_.at(from_vertix).begin(); it != graph_.at(from_vertix).end(); it++)
            if (*it == to_vertix)
            {
                graph_.at(from_vertix).erase(it);
                return;
            }
    }
    void construct_by_list(const std::vector < std::vector <int> > &graph)
    {
        clear();
        graph_ = graph;
    }
    void construct_by_matrix(const std::vector < std::vector <bool> > &graph)
    {
        clear();
        graph_.resize(graph.size());
        for (size_t node = 0; node < graph.size(); node++)
            for (size_t to = 0; to < graph.size(); to++)
                if (graph.at(node).at(to))
                    graph_.at(node).push_back(to);
    }

    void foreach_neighbour(int vertix, std::function <void(int)> visitor) const
    {
        for (auto it = graph_.at(vertix).begin(); it != graph_.at(vertix).end(); it++)
            visitor(*it);
    }
    bool is_edged(int from_vertix, int to_vertix) const
    {
        for (auto it = graph_.at(from_vertix).begin(); it != graph_.at(from_vertix).end(); it++)
            if (*it == to_vertix)
                return true;
        return false;
    }

    size_t byte_size() const
    {
        size_t size_of_edges = 0;
        for (auto it = graph_.begin(); it != graph_.end(); it++)
            size_of_edges += it -> capacity();
        return sizeof(std::vector< std::vector <int> >) + sizeof(std::vector <int> ) * graph_.capacity() +
               size_of_edges * sizeof(int);
    }
    size_t byte_size(size_t number_of_vertices, size_t number_of_edges) const
    {
        return sizeof(std::vector< std::vector <int> >) + sizeof(std::vector <int> ) * number_of_vertices +
               number_of_edges * sizeof(int);
    }
};
